BZOJ2154 Crash的数字表格 <莫比乌斯反演>

Problem

Crash的数字表格

Description

今天的数学课上，小朋友学习了最小公倍数。对于两个正整数和，表示能同时被和整除的最小正整数。例如，。回到家后，还在想着课上学的东西，为了研究最小公倍数，他画了一张的表格。每个格子里写了一个数字，其中第行第列的那个格子里写着数为。看着这个表格，想到了很多可以思考的问题。不过他最想解决的问题却是一个十分简单的问题：这个表格中所有数的和是多少。当和很大时，就束手无策了，因此他找到了聪明的你用程序帮他解决这个问题。由于最终结果可能会很大，只想知道表格里所有数的和的值。

Input

输入的第一行包含两个正整数，分别表示和。

Output

输出一个正整数，表示表格中所有数的和的值。

Sample Input

4 5

Sample Output

HINT

的数据满足。

标签：莫比乌斯反演

Solution

由以上推导，可见和是可以根号分块的，在外层对进行分块，在每个值相同的块中，对进行分块以求出带回外层算贡献。

综上，外层复杂度为，内层复杂度为，总时间复杂度为。

其实可以做得更快，详见加强版BZOJ2693。

Code

#include <bits/stdc++.h>
#define MAX_N 10000000
#define MOD 20101009
using namespace std;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt n, m, ans, s[MAX_N+5];
int cnt, pri[MAX_N+5], mu[MAX_N+5];
bool NotPri[MAX_N+5];
void getMu() {
    NotPri[1] = true, mu[1] = 1;
    for (int i = 2; i <= min(n,m); i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > min(n,m)) break;
            NotPri[i*pri[j]] = true;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i];
            else {mu[i*pri[j]] = 0; break;}
        }
    }
    for (int i = 1; i <= min(n,m); i++) s[i] = (s[i-1]+1LL*mu[i]*i*i%MOD)%MOD;
}
lnt f(lnt p, lnt q) {
    lnt ret = 0;
    for (lnt l = 1, r; l <= min(p, q); l = r+1)
        r = min(p/(p/l), q/(q/l)), 
        (ret += (p/l*(p/l+1)/2%MOD)*(q/l*(q/l+1)/2%MOD)%MOD*(s[r]-s[l-1])%MOD) %= MOD;
    return ret;
}
int main() {
    read(n), read(m), getMu();
    for (lnt l = 1, r; l <= min(n, m); l = r+1)
        r = min(n/(n/l), m/(m/l)), (ans += (l+r)*(r-l+1)/2%MOD*f(n/l, m/l)%MOD) %= MOD;
    return printf("%lld", (ans+MOD)%MOD), 0;
}